package com.azure.code.graph.topologicalSorting;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 课程表II  210 是207的升级
 * 现在你总共有 numCourses 门课需要选，记为0到numCourses - 1。
 * 给你一个数组prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修bi 。
 *
 * 例如，想要学习课程 0 ，你需要先完成课程1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种 就可以了。
 * 如果不可能完成所有课程，返回 一个空数组 。
 *
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：[0,1]
 * 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
 *
 * 返回拓扑排序
 *
 */
public class Courses_210 {
    boolean[] onPath;
    boolean[] visited;
    boolean hasCycle;
    LinkedList<Integer> path;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        onPath = new boolean[numCourses];
        visited = new boolean[numCourses];
        hasCycle = false;
        path = new LinkedList<>();
        List<Integer>[] graph = buildGraph(numCourses,prerequisites);

        for (int i = 0; i < numCourses; i++) {
            traverse(graph,i);
        }
        // 有环图 无法进行拓扑排序
        if(hasCycle){
            return new int[]{};
        }
        int[] res = new int[numCourses];
        for (int i = 0;i<numCourses;i++){
            res[i] = path.get(i);
        }
        return res;
    }

    private void traverse(List<Integer>[] graph, int s) {
        if(onPath[s]){
            hasCycle = true;
        }
        if(visited[s]||hasCycle){
            return;
        }
        onPath[s] = true;
        visited[s] = true;
        for (Integer x : graph[s]) {
            traverse(graph,x);
        }
        path.addFirst(s);
        onPath[s] = false;
    }


    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
        LinkedList<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0;i < numCourses;i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : prerequisites) {
            graph[edge[1]].add(edge[0]);
        }
        return graph;
    }
}
